Geographic information systems provide for the archiving, retrieving, and manipulating of data that has been stored and indexed according to geographic coordinates of its elements. A geographic information system generally includes a variety of data types, including imagery, maps, tables, vector data (e.g. vector representations of roads, parcels, buildings, etc.) and other data. Improvements in computer processing power and broadband technology have led to the development of interactive geographic information systems that allow for the navigating and displaying of geographic imagery. Some interactive geographic information systems provide a user interface with navigation controls for navigating cities, neighborhoods, geographic areas and other terrain in two or three dimensions. The navigation controls can enable users to tilt, pan, rotate, zoom, and activate views of terrain, buildings, and other objects from different perspectives at a geographic area of interest. An example of an interactive geographic information system for navigating geographic imagery is the Google Earth™ virtual globe application developed by Google Inc.
Due to the massive volume of data in certain geographic information systems, the data can be spatially partitioned into manageable pieces to facilitate processing of the data. For instance, in an interactive geographic information system for displaying and navigating imagery, the geospatially organized data can be spatially partitioned into manageable pieces for fetching and rendering data associated only with the visible portion of the geographic area in the user interface for viewing and navigating the geographic imagery. The geospatially organized data can be arranged in a data structure, such as a quadtree or octree data structure, to facilitate fetching, culling, and level of detail management of the data.
Typical spatial partitioning schemes, such as spatial partitioning schemes used in three-dimensional graphics applications in gaming, spatially partition data into two or three dimensional Cartesian spaces, i.e. boxes in a coordinate system having an x-axis, y-axis, and a z-axis. For a large geographic information system, such as a virtual globe application providing for the rendering of an entire planet or other spheriod (e.g. the Earth, Moon, Mars, etc.), the source data is often available in a spherical projection, i.e. latitude, longitude, and altitude coordinates. Mapping the source data in these cases into a Cartesian spatial partitioning scheme can be cumbersome and non-trivial.
In addition, existing spatial partitioning schemes associated with spherical or near spherical objects, such as a planet, geoid, or other spheroid, can result in distortions caused by the natural compression of longitude in geographic areas proximate the poles of the spherical or near spherical object. For instance, geographic information systems that spatially partition data using a flat latitude/longitude equirectangular projection of a planet (e.g. a plate carree) to map an image to the spherical surface of the planet can result in tessellation problems in areas adjacent the poles of the planet. For instance, the tessellation of the Earth into a quadtree data structure with each quad node being square in terms of latitude and longitude can result in compression of the quad node at geographic locations adjacent the poles. Indeed quad nodes that touch the poles can become triangles, resulting in reduced image quality when viewing imagery of the poles in the interactive geographic information system.